import java.util.*;

/**
 * @author LKQ
 * @date 2022/6/19 16:01
 * @description
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] as = {-5, -10, 12, -10};
        solution.asteroidCollision(as);
    }
    public int[] asteroidCollision(int[] asteroids) {
        Deque<Integer> d = new ArrayDeque<>();
        for (int i = 0; i < asteroids.length; i++) {
            boolean isAdd = true;
            // 栈顶为负，后来的负或者正都无法相撞，直接加入
            while (!d.isEmpty() && (d.peek() > 0 && asteroids[i] < 0)) {
                // 栈顶为正向右，来负向左，相撞
                if (Math.abs(d.peek()) < Math.abs(asteroids[i])) {
                    d.pollFirst();
                }else if (Math.abs(d.peek()) == Math.abs(asteroids[i])) {
                    d.pollFirst();
                    isAdd = false;
                    break;
                }else {
                    isAdd = false;
                    break;
                }
            }
            if (isAdd) {
                d.push(asteroids[i]);
            }
        }
        int[] ans = new int[d.size()];
        for(int i = d.size() - 1; i >= 0; i--) {
            ans[i] = d.pollFirst();
        }
        return ans;
    }
}
